# 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
#
#  本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
#
#  示例:
#
#  给定的有序链表： [-10, -3, 0, 5, 9],
#
# 一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
#
#       0
#      / \
#    -3   9
#    /   /
#  -10  5
#
#  Related Topics 深度优先搜索 链表
#  👍 306 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.

# todo fixme 中序遍历
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """

        # 找中位数节点，利用快慢指针
        def get_median(head, tail):
            fast = head
            slow = head
            while fast != tail and fast.next != tail:
                fast = fast.next.next
                slow = slow.next
            return slow

        def build_bst(left, right):
            # 左右指针相等，只有根节点
            if left == right:
                return None
            median = get_median(left, right)

            root = TreeNode(median.val, None, None)
            root.left = build_bst(left, median)
            root.right = build_bst(median.next, right)

            return root

        tree = build_bst(head, None)
        #     层次遍历
        stack = []
        res = []
        stack.append(tree)
        while len(stack) != 0:

            nodelist = stack[:]

            del stack[:]
            for node in nodelist:
                res.append(node.val)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)

        return res


# leetcode submit region end(Prohibit modification and deletion)

# -10, -3, 0, 5, 9
head = ListNode(-10, ListNode(-3, ListNode(0, ListNode(5, ListNode(9, None)))))

print(Solution().sortedListToBST(head))
